1. Field of Invention
The present invention relates generally to the field of computer coding and pertains more particularly to coding the bit-planes of an array of numbers.
2. Discussion of the Prior Art
With the advent of the computer and the Internet, man is living increasingly in an information age. The storage and transmission of information or data has taken on a lab heightened importance. Unfortunately, storage space and transmission bandwidth are not unlimited. Modem computer systems have become increasingly graphics intensive. Dedicated special purpose memories and hardware have been developed to meet this need. New and improved graphics file formats and communication protocols are being developed as well. As graphics technologies and products become more prevalent in consumer areas, slim profit margins are demanding the utmost efficiencies. Compression is necessary to achieve efficiency in database representation to conserve disk storage, system memory, cache memory, and special purpose memories. Additional savings can be achieved by conserving bus bandwidths, which becomes more critical with unified computer architectures where graphics and system memory are one and the same.
Data compression is often used to reduce the cost of storing large data files on computers as well as to reduce the time for transmitting large data files between computers. Several compression techniques exist. One technique is to transform the data from its original form into a second form which is easier to manipulate. In the so-called “transform methods” data is transformed into coefficients that represent the data in a frequency domain. Coefficients may be quantized without significantly affecting the quality of data that is reconstructed. This is a form of lossy compression. Lossy compression refers to compression with some effect on the rendered output. Redundancy in the coefficients may then be reduced or eliminated without affecting the quality of the reconstructed data. This is a form of lossless compression. Lossless compression refers to compression with no effect on the rendered output.
One well known class of transforms are Wavelet transforms. The Wavelet transforms may be used to perform subband decomposition and produce coefficients that describe the data in a hierarchical multiscale representation. Wavelet transforms have proven useful for the compression of images and the analysis of signals. They have been proposed as the transform for the emerging JPEG-2000 standard.
Among the advantages of the Wavelet transforms is that the transform coefficients can be ordered in a hierarchical structure and transmitted in an “embedded bitstream.” The embedded bitstream has a property whereby prefixes of the bitstream yield a continuum of lower rate descriptions of the data at the highest possible levels of quality. If the embedded bitstream is truncated during transmission of image data, for instance, the information already transmitted will allow an entire image to be reconstructed. The quality of the reconstructed image is dependent upon the amount of information transmitted. As additional information is transmitted, the quality of the reconstructed image is improved. If the entire bitstream is transmitted without truncation, a lossless or near-lossless image can be reconstructed. If an embedded bitstream is truncated, a complete image of reduced quality can be reconstructed from the transmitted bits. In contrast, truncation of a non-embedded transmission might only allow several rows of an image to be reconstructed.
The transmission just described is often referred to as a progressive-by-quality or SNR (signal to noise ratio) scalable image transmission. The coefficients are converted to binary and described by bit-planes. The most significant coefficient bits, that is, the coefficient bits conveying the most important information, are transmitted first. The lesser significant coefficient bits are then transmitted in order of decreasing importance with the least significant coefficient bits being transmitted last.
Another type of transmission is often referred to as progressive-by-resolution transmission. The progressive-by-resolution transmission involves ordering the coefficients according to different levels of image resolution. The different levels are identified by markers in the embedded bitstream. A computer may use the markers to parse the bitstream and transmit the data for the coefficients corresponding to a resolution that is specified by the receiving computer. The receiving computer can then reconstruct an image according to the specified resolution.
A number of coding algorithms have been proposed for ordering the description of the transform coefficients such that the retained number of bits of the description can produce the best quality image. For example, algorithms have been proposed by Shapiro, known as the “Zerotree” algorithm, and an improvement thereon by Said-Pearlman, known as the “SPIHT” algorithm, among others. However, there are a number of problems associated with the Zerotree based algorithms. Among these problems is that Zerotree coders rely on the use of a complex arrangement of lists and pointers. Further, the Zerotree coders minimize image distortion only at bit-plane boundaries. As long as the transmission is truncated at a bit-plane boundary, the image distortion will be minimized. However, if a transmission is truncated at a point other than a bit-plane boundary, the image distortion will not be minimized.
A definite need exists for a system having an ability to meet the efficiency requirements of graphics intensive computer systems. In particular, a need exists for a system which is capable of ordering the description of the transform coefficients in a simple and fast manner. Ideally, such a system would have a lower cost and a higher productivity than conventional systems. With a system of this type, system performance can be enhanced. A primary purpose of the present invention is to solve this need and provide further, related advantages.